package com.skh.string;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.Comparator;
import java.util.List;

/**
 * @Author skh
 * @Date 2020/4/12 15:21
 * @Desc  数组中的字符串匹配
 */
public class StringMatching {

    /**
     * 给你一个字符串数组 words ，数组中的每个字符串都可以看作是一个单词。请你按 任意 顺序返回 words 中是其他单词的子字符串的所有单词。
     *
     * 如果你可以删除 words[j] 最左侧和/或最右侧的若干字符得到 word[i] ，那么字符串 words[i] 就是 words[j] 的一个子字符串。
     *
     *  
     *
     * 示例 1：
     *
     * 输入：words = ["mass","as","hero","superhero"]
     * 输出：["as","hero"]
     * 解释："as" 是 "mass" 的子字符串，"hero" 是 "superhero" 的子字符串。
     * ["hero","as"] 也是有效的答案。
     * 示例 2：
     *
     * 输入：words = ["leetcode","et","code"]
     * 输出：["et","code"]
     * 解释："et" 和 "code" 都是 "leetcode" 的子字符串。
     * 示例 3：
     *
     * 输入：words = ["blue","green","bu"]
     * 输出：[]
     */


    /**
     * 思路一:两次遍历,第一遍将所有字符串拼接起来,第二遍判断索引位置
     * @param words
     * @return
     */
    public List<String> stringMatching(String[] words) {
        StringBuilder sb = new StringBuilder();
        for (String word : words) {
            sb.append(word).append(",");
        }

        String str = sb.toString();
        List<String> resultList = new ArrayList<>();

        for (String word : words) {
            if (str.indexOf(word) != str.lastIndexOf(word)) {
                resultList.add(word);
            }
        }

        return resultList;
    }

    public List<String> stringMatching2(String[] words) {
        List<String> resultList = new ArrayList<>();

        Arrays.sort(words, new Comparator<String>() {
            @Override
            public int compare(String s1, String s2) {
                return s1.length() - s2.length();
            }
        });

        for (int i = 0; i < words.length; i++) {
            for (int j = i+1; j < words.length; j++) {
                if (words[j].contains(words[i])) {
                    resultList.add(words[i]);
                    break;
                }
            }
        }

        return resultList;
    }
}
